// 给定不同面额的硬币 coins 和一个总金额 amount。
// 编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
// 如果没有任何一种硬币组合能组成总金额，返回 -1。

// 你可以认为每种硬币的数量是无限的。

const coinChange = function (coins: number[], amount: number): number {
    // coins.sort((a, b) => b - a); // 排序硬币面值，降序，看题目而定
    // dp数组对应：当前索引下所需的最少硬币数
    const dp: number[] = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // 起始状态
    for (let currAmount = 1; currAmount <= amount; currAmount++) {
        for (let i = 0; i < coins.length; i++) {
            // 如果当前硬币面值大于当前金额，则肯定凑不出来直接跳过
            if (coins[i] > currAmount) continue;
            // 状态转移方程，硬币凑出来的情况，当前硬币数 + 1
            dp[currAmount] = Math.min(dp[currAmount - coins[i]] + 1, dp[currAmount]);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};


// 这道题目是一道非常经典的动态规划题目，考察的是可行性组合问题
// 我们主要看一下，每一次循环中是如何做决策的。
// 其中每一次循环都包含一个小循环，这个小循环会遍历所有的面值
// 我们先看当前面额总值是否小于当前硬币面额。如果是，则说明
// 前硬币面值大于当前金额，组合肯定不存在，直接进入下一轮循环。
// 否则，就可以认为已经使用了这一枚硬币，这时我们要作出决策：
// 如果采纳了这枚硬币，则凑的硬币数量需要 +1，此时状态即为dp[currAmount - coins[i]] + 1
// 如果不采纳这枚硬币，则凑的硬币数量和之前不变，dp[currAmount]
// 显然，硬币找零问题是求最值问题（即最少需要几枚硬币凑出总额 k）。因此，我们
// 在这里作出决策，在状态 A 与状态 B 中谁的硬币数量更少，即取最小值 min（是否采纳当前硬币）
// 当循环结束后，即可得到最后的结果